# LeetCode 474、一和零
# 一、题目描述
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]仅由'0'和'1'组成1 <= m, n <= 100
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 一和零（LeetCode 474）：https://leetcode.cn/problems/ones-and-zeroes/
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 获取字符串数组的长度
int len = strs.length;
// dp[i][j][k] 表示
// 1、从前 i 个字符串中选出若干个
// 2、在使得其中 0 的数目不超过 j
// 3、1 的数目不超过 k 的情况下能够选出的最多的字符串数目
int[][][] dp = new int[len + 1][m + 1][n + 1];
// 开始填充这个三维数组
// 1、物品一个一个尝试
// 2、容量一点一点尝试
// 3、每个物品分类讨论：选与不选
for (int i = 1; i <= len; i++) {
// 注意到 i 是从下标 1 开始访问的
// 对于字符串数组 strs 来说，区间 [ 0 , 1 ] 的这个字符串是 strs[0]
// 也就是说，区间 [ 0 , i ] 的最后一个字符串是 strs[i - 1]
// 需要讨论 strs[i - 1] 能否加入到我们的【背包当中】
String currentStr = strs[ i - 1 ];
// 统计 strs[ i - 1 ] 中 0 的数量
int zeroNum = countZeroNumber(currentStr);
// 统计 strs[ i - 1 ] 中 1 的数量
int oneNum = countOneNumber(currentStr);
// 01 背包问题，开始讨论
for( int j = 0 ; j <= m ; j++){
for( int k = 0 ; k <= n ; k++){
// 1、如果发现目前能够使用的 0 的个数 j 小于了当前字符串中 0 的数量
// 2、如果发现目前能够使用的 1 的个数 k 小于了当前字符串中 1 的数量
if( j < zeroNum || k < oneNum){
// 意味着当前这个字符串 currentStr 无法放入到背包当中
// 此时，不选择当前考虑的这个字符串
// 能够得到的字符串数目的最大值可以通过前 i - 1 个字符串中得到结果
dp[ i ][ j ][ k ] = dp[ i - 1 ][ j ][ k ];
// 否则，当前这个字符串有资格加入都背包当中
}else{
// 在有资格的情况下，可以选，也可以不选
// 1、不选， 能够得到的字符串数目的最大值可以通过前 i - 1 个字符串中得到结果
// 2、选，那么当前这个字符串必然加入进去，子集长度加 1
// 同时 0 的个数剩下 j - zeroNum，1 的个数剩下 k - oneNum
// 需要从前 i - 1 个字符串中去凑这些 0 和 1
dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeroNum][k - oneNum] + 1);
}
}
}
}
// 返回结果
return dp[len][m][n];
}
// 统计字符串 str 中 0 的个数
private int countZeroNumber(String str){
int count = 0;
for(char c : str.toCharArray()){
if( c == '0'){
count++;
}
}
return count;
}
// 统计字符串 str 中 1 的个数
private int countOneNumber(String str){
int count = 0;
for(char c : str.toCharArray()){
if( c == '1'){
count++;
}
}
return count;
}
}
# **2、**C++ 代码
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// 获取字符串数组的长度
int len = strs.size();
// dp[i][j][k] 表示
// 1、从前 i 个字符串中选出若干个
// 2、在使得其中 0 的数目不超过 j
// 3、1 的数目不超过 k 的情况下能够选出的最多的字符串数目
vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
// 开始填充这个三维数组
// 1、物品一个一个尝试
// 2、容量一点一点尝试
// 3、每个物品分类讨论：选与不选
for (int i = 1; i <= len; i++) {
// 注意到 i 是从下标 1 开始访问的
// 对于字符串数组 strs 来说，区间 [ 0 , 1 ] 的这个字符串是 strs[0]
// 也就是说，区间 [ 0 , i ] 的最后一个字符串是 strs[i - 1]
// 需要讨论 strs[i - 1] 能否加入到我们的【背包当中】
string currentStr = strs[ i - 1 ];
// 统计 strs[ i - 1 ] 中 0 的数量
int zeroNum = countZeroNumber(currentStr);
// 统计 strs[ i - 1 ] 中 1 的数量
int oneNum = countOneNumber(currentStr);
// 01 背包问题，开始讨论
for( int j = 0 ; j <= m ; j++){
for( int k = 0 ; k <= n ; k++){
// 1、如果发现目前能够使用的 0 的个数 j 小于了当前字符串中 0 的数量
// 2、如果发现目前能够使用的 1 的个数 k 小于了当前字符串中 1 的数量
if( j < zeroNum || k < oneNum){
// 意味着当前这个字符串 currentStr 无法放入到背包当中
// 此时，不选择当前考虑的这个字符串
// 能够得到的字符串数目的最大值可以通过前 i - 1 个字符串中得到结果
dp[ i ][ j ][ k ] = dp[ i - 1 ][ j ][ k ];
// 否则，当前这个字符串有资格加入都背包当中
}else{
// 在有资格的情况下，可以选，也可以不选
// 1、不选， 能够得到的字符串数目的最大值可以通过前 i - 1 个字符串中得到结果
// 2、选，那么当前这个字符串必然加入进去，子集长度加 1
// 同时 0 的个数剩下 j - zeroNum，1 的个数剩下 k - oneNum
// 需要从前 i - 1 个字符串中去凑这些 0 和 1
dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zeroNum][k - oneNum] + 1);
}
}
}
}
// 返回结果
return dp[len][m][n];
}
private:
int countZeroNumber(string str){
int count = 0;
for(int i = 0 ; i < str.size() ; i++){
if( str[i] == '0'){
count++;
}
}
return count;
}
private:
int countOneNumber(string str){
int count = 0;
for(int i = 0 ; i < str.size() ; i++){
if( str[i] == '1'){
count++;
}
}
return count;
}
};
# 3、Python 代码
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
length = len(strs)
# dp[i][j][k] 表示
# 1、从前 i 个字符串中选出若干个
# 2、在使得其中 0 的数目不超过 j
# 3、1 的数目不超过 k 的情况下能够选出的最多的字符串数目
dp = [[[0] * ( n + 1 ) for _ in range( m + 1)] for _ in range(length+1)]
# 开始填充这个三维数组
# 1、物品一个一个尝试
# 2、容量一点一点尝试
# 3、每个物品分类讨论：选与不选
for i in range(1, length+1):
# 注意到 i 是从下标 1 开始访问的
# 对于字符串数组 strs 来说，区间 [ 0 , 1 ] 的这个字符串是 strs[0]
# 也就是说，区间 [ 0 , i ] 的最后一个字符串是 strs[i - 1]
# 需要讨论 strs[i - 1] 能否加入到我们的【背包当中】
# 统计 strs[ i - 1 ] 中 0 的数量
c0 = strs[i-1].count('0')
# 统计 strs[ i - 1 ] 中 1 的数量
c1 = len(strs[i-1]) - c0
for j in range(m+1):
for k in range(n+1):
# 1、如果发现目前能够使用的 0 的个数 j 小于了当前字符串中 0 的数量
# 2、如果发现目前能够使用的 1 的个数 k 小于了当前字符串中 1 的数量
if j < c0 or k < c1:
dp[i][j][k] = dp[i-1][j][k]
else:
# 在有资格的情况下，可以选，也可以不选
# 1、不选， 能够得到的字符串数目的最大值可以通过前 i - 1 个字符串中得到结果
# 2、选，那么当前这个字符串必然加入进去，子集长度加 1
# 同时 0 的个数剩下 j - zeroNum，1 的个数剩下 k - oneNum
# 需要从前 i - 1 个字符串中去凑这些 0 和 1
dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][j-c0][k-c1] + 1 )
return dp[length][m][n]